');}

NOIP2008 普及组

Author Avatar
Actinoi 7月 24, 2019

T1:ISBN号码

题目描述

每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括 9 位数字、 1 位识别码和 3 位分隔符，其规定格式如x-xxx-xxxxx-x，其中符号-就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符-之后的三位数字代表出版社，例如 670 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 1 加上次位数字乘以 2 ……以此类推，用所得的结果 mod11 ，所得的余数即为识别码，如果余数为 10 ，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码 4 是这样得到的：对067082162这 9 个数字，从左至右，分别乘以 1,2,…,9 再求和，即 0×1+6×2+……+2×9=158 ，然后取 158mod11 的结果 4 作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出Right；如果错误，则输出你认为是正确的ISBN号码。

输入输出格式

输入格式：

一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。

输出格式：

一行，假如输入的ISBN号码的识别码正确，那么输出Right，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符-）。

输入输出样例

输入样例#1：

  1. 0-670-82162-4

输出样例#1：

  1. Right

输入样例#2：

  1. 0-670-82162-0

输出样例#2：

  1. 0-670-82162-4

说明

2008普及组第一题

题解：

 ​本题直接模拟就可以。设置一个变量 k ，表该这个数字该乘几了。然后读入这个 ISBN 号码，如果是数字的话那么便 ×k ，最后让识别码 mod\ 11 ，接着特判一下识别码是不是 X 就可以了。

  1. #include <iostream>
  2. using namespace std;
  3. char ISBN[15]; //存储图书ISBN号
  4. int main() {
  5.     int num = 0; //存储正确的识别码
  6.     int k = 1; //第几个数字
  7.     for (int i = 1; i <= 12; i++) {
  8.         cin >> ISBN[i];
  9.         if (ISBN[i] >= '0' && ISBN[i] <= '9') { //找到一个数字
  10.             num += ((ISBN[i] - '0') * k);
  11.             k++;
  12.         }
  13.     }
  14.     num %= 11; //将所得的结果mod11，所得的余数即为识别码
  15.     cin >> ISBN[13]; //读入识别码
  16.     if (num != 10)
  17.         if (num == ISBN[13] - '0')
  18.             cout << "Right" << endl;
  19.         else {
  20.             for (int i = 1; i <= 12; i++)
  21.                 cout << ISBN[i];
  22.             cout << num << endl;
  23.         }
  24.     else
  25.         if (ISBN[13] == 'X')
  26.             cout << "Right" << endl;
  27.         else {
  28.             for (int i = 1; i <= 12; i++)
  29.                 cout << ISBN[i];
  30.             cout << "X" << endl;
  31.         }
  32.     return 0;
  33. }

T2:排座椅

题目描述

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 D 对同学上课时会交头接耳。

同学们在教室中坐成了 M 行 N 列，坐在第 i 行第j列的同学的位置是 (i,j) ，为了方便同学们进出，在教室中设置了 K 条横向的通道， L 条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了 2 个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

输入输出格式

输入格式：

第一行，有 5 个用空格隔开的整数，分别是 M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)

接下来的 D 行，每行有 4 个用空格隔开的整数。第 i 行的 4 个整数 Xi,Yi,Pi,Qi ，表示坐在位置 (Xi,Yi) 与 (Pi,Qi) 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

输入数据保证最优方案的唯一性。

输出格式：

共两行。 第一行包含 K 个整数 a1,a2,…,aK ​，表示第 a1 ​行和 a1+1 行之间、第 a−2 行和 a2+1 行之间、…、第 aK 行和第 aK+1 行之间要开辟通道，其中 ai<ai+1 ，每两个整数之间用空格隔开（行尾没有空格）。

第二行包含 L 个整数 b1,b2,…,bL ，表示第 b1 列和 b1+1 列之间、第 b2 列和 b2+1 列之间、…、第 bL 列和第 bL+1 列之间要开辟通道，其中 bi<bi+1 ，每两个整数之间用空格隔开（列尾没有空格）。

输入输出样例

输入样例#1：

  1. 4 5 1 2 3
  2. 4 2 4 3
  3. 2 3 3 3
  4. 2 5 2 4

输出样例#1：

  1. 2
  2. 2 4

说明

上图中用符号*、※、+标出了 3 对会交头接耳的学生的位置，图中 3 条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

2008年普及组第二题

题解：

 ​我们读完这道题目，就想到本题可以用贪心的思想来解决。

 ​在读入 x,y,p,q 之后，我们找哪里可以将两人分开。例如，当 x=p 时，则代表两人的横坐标相同，纵坐标不同，所以应该在平行于 y 轴的地方将两人分开。我们用 L 数组表示平行于 y 轴的道路，用 H 数组表示平行于 x 轴的道路。 则当 x=p 时， L[min(y,\ q)]++ ；当 y = q 时，应该在平行于 x 轴的地方将两人分开，所以 H[min(x,\ p)]++ 。

 ​接着，我们依次枚举 H 数组最大的前 k 项与 L 数组最大的前 l 项，将其按序号从小到大排序输出，便得到我们的答案辣！

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int H[1001], L[1001];
  5. int a[1001]; //存储要选择的数字
  6. int main() {
  7.     int m, n, k, l, d; //同学们在教室中坐成了m行m列，设置了K条横向的通道，L条纵向的通道，只有有限的D对同学上课时会交头接耳
  8.     cin >> m >> n >> k >> l >> d;
  9.     int x, y, p, q; //表示坐在位置(x,y)与(p,q)的两个同学会交头接耳
  10.     for (int i = 1; i <= d; i++) {
  11.         cin >> x >> y >> p >> q;
  12.         if (x == p) //两人的横坐标相同，纵坐标不同，应在L数组将两人分开
  13.             L[min(y, q)]++;
  14.         else //两人的纵坐标相同，横坐标不同，应在H数组将两人分开
  15.             H[min(x, p)]++;
  16.     }
  17.     int w = 0;
  18.     for (int i = 1; i <= k; i++) { //选横着要在哪里设走廊
  19.         int maxx = 0, bh = 0;
  20.         for (int j = 1; j <= m; j++)
  21.             if (H[j] > maxx) {
  22.                 maxx = H[j];
  23.                 bh = j;
  24.                 
  25.             }
  26.         w++;
  27.         a[w] = bh;
  28.         H[bh] = 0;
  29.     }
  30.     sort(a + 1, a + 1 + k);
  31.     for (int i = 1; i <= k; i++)
  32.         cout << a[i] << " ";
  33.     w = 0;
  34.     cout << endl;
  35.     for (int i = 1; i <= l; i++) { //选竖着要在哪里设走廊
  36.         int maxx = 0, bh = 0;
  37.         for (int j = 1; j <= n; j++)
  38.             if (L[j] > maxx) {
  39.                 maxx = L[j];
  40.                 bh = j;
  41.             }
  42.         w++;
  43.         a[w] = bh;
  44.         L[bh] = 0;
  45.     }
  46.     sort(a + 1, a + 1 + l);
  47.     for (int i = 1; i <= l; i++)
  48.         cout << a[i] << " ";
  49.     return 0;
  50. }

T3:传球游戏

题目描述

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。

游戏规则是这样的： n 个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了 m 次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学 1 号、 2 号、 3 号，并假设小蛮为 1 号，球传了 3 次回到小蛮手里的方式有 1 -> 2 -> 3 -> 1 和 1 -> 3 -> 2 -> 1 ，共 2 种。

输入输出格式

输入格式：

一行，有两个用空格隔开的整数 n,m(3≤n≤30,1≤m≤30) 。

输出格式：

1 个整数，表示符合题意的方法数。

输入输出样例

输入样例#1：

  1. 3 3

输出样例#1：

  1. 2

说明

40\% 的数据满足： 3≤n≤30,1≤m≤20

100\% 的数据满足： 3≤n≤30,1≤m≤30

2008普及组第三题

题解：

 ​一个 DP 问题。

 ​游戏开始之后，每个人手中的球要么是从他左边传过来的，要么是从他右边传过来的，所以第 i 轮时球回到第 j 个人手里的方式总数也就是上一轮时球回到第 j - 1 个人的方案总数 + 上一轮时球回到第 j + 1 个人的方案总数。我们化环为链，用 DP[i][j] 来表示在第 i 轮时回到第 j 个人手里的方式总数。因此，便可以得到 DP[i][j]\ =\ DP[i-1][j-1]\ + \ DP[i-1][j+1] 。考虑边界条件，在一开始时，球在第一个人手里，所以 DP[0][1]\ =\ 1 。然后考虑到特殊情况，当 i = 1 或 i = n 时，要进行特殊处理，特殊处理比较简单，所以。。。就直接看代码吧！

  1. #include <iostream>
  2. using namespace std;
  3. int DP[31][31];
  4. int main() {
  5.     int n, m;
  6.     cin >> n >> m; //n个同学m轮
  7.     DP[0][1] = 1; //边界条件
  8.     
  9.     for (int i = 1; i <= m; i++)
  10.         for (int j = 1; j <= n; j++)
  11.             if (j == 1)
  12.                 DP[i][j] = DP[i - 1][j + 1] + DP[i - 1][n];
  13.             else if (j == n)
  14.                 DP[i][j] = DP[i - 1][1] + DP[i - 1][j - 1];
  15.             else
  16.                 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1];
  17.     
  18.     DP[m][1] = DP[m - 1][2] + DP[m - 1][n];
  19.     cout << DP[m][1] << endl;
  20.     return 0;
  21. }

T4:立体图

题目描述

小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。

小渊有一块面积为 m×n 的矩形区域，上面有 m×n 个边长为 1 的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是 1 ），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：

  1.   +---+ 
  2.  /   /| 
  3. +---+ | 
  4. |   | + 
  5. |   |/ 
  6. +---+

每个顶点用 1 个加号’+’表示，长用 3 个”-“表示，宽用 1 个”/”表示，高用两个”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为 43 ， 45 ， 47 ， 124 。字符’.’（ASCII码 46 ）需要作为背景输出，即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则：

若两块积木左右相邻，图示为：

  1. ..+---+---+ 
  2. ./   /   /| 
  3. +---+---+ | 
  4. |   |   | + 
  5. |   |   |/. 
  6. +---+---+..

若两块积木上下相邻，图示为：

  1. ..+---+ 
  2. ./   /| 
  3. +---+ | 
  4. |   | + 
  5. |   |/| 
  6. +---+ | 
  7. |   | + 
  8. |   |/. 
  9. +---+..

若两块积木前后相邻，图示为：

  1. ....+---+ 
  2. .../   /| 
  3. ..+---+ | 
  4. ./   /| + 
  5. +---+ |/. 
  6. |   | +.. 
  7. |   |/... 
  8. +---+....

立体图中，定义位于第 (m,1) 的格子（即第 m 行第 1 列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。

输入输出格式

输入格式：

第一行有用空格隔开的 2 个整数 m 和 n ，表示有 m×n 个格子 (1≤m,n≤50) 。

接下来的 m 行，是一个 m×n 的矩阵，每行有 n 个用空格隔开的整数，其中第 i 行第 j 列上的整数表示第 i 行第 j 列的格子上摞有多少个积木（ 1≤ 每个格子上的积木数 ≤100 ）。

输出格式：

输出包含题目要求的立体图，是一个 K 行 L 列的字符串矩阵，其中 K 和 L 表示最少需要 K 行 L 列才能按规定输出立体图。

输入输出样例

输入样例#1：

  1. 3 4
  2. 2 2 1 2
  3. 2 2 1 1
  4. 3 2 1 2

输出样例#1：

  1. ......+---+---+...+---+
  2. ..+---+  /   /|../   /|
  3. ./   /|-+---+ |.+---+ |
  4. +---+ |/   /| +-|   | +
  5. |   | +---+ |/+---+ |/|
  6. |   |/   /| +/   /|-+ |
  7. +---+---+ |/+---+ |/| +
  8. |   |   | +-|   | + |/.
  9. |   |   |/  |   |/| +..
  10. +---+---+---+---+ |/...
  11. |   |   |   |   | +....
  12. |   |   |   |   |/.....
  13. +---+---+---+---+......

说明

NOIP2008普及组第四题

题解：

 ​这个题用打表的方法就可以。。。按照从后先前，从下向上，从左向右地顺序构建立体图就能做出此题。

  1. #include <iostream>
  2. using namespace std;
  3. char canvas[1001][1001];
  4. int num[51][51]; //第i行第j列的个子上摞有多少个积木
  5. int m, n;
  6. int c, k; //计算画布的长度与宽度
  7. void draw(int x, int y) {
  8.     canvas[x][y]  =  '+';
  9.     canvas[x][y + 1]  =  '-';
  10.     canvas[x][y + 2]  =  '-';
  11.     canvas[x][y + 3]  =  '-';
  12.     canvas[x][y + 4] = '+';
  13.     canvas[x - 1][y]  =  '|';
  14.     canvas[x - 1][y + 1]  =  ' ';
  15.     canvas[x - 1][y + 2] = ' ';
  16.     canvas[x - 1][y +3] = ' ';
  17.     canvas[x - 1][y + 4] = '|';
  18.     canvas[x - 1][y + 5] = '/';
  19.     canvas[x - 2][y] = '|';
  20.     canvas[x - 2][y + 1] = ' ';
  21.     canvas[x - 2][y + 2] = ' ';
  22.     canvas[x - 2][y + 3] = ' ';
  23.     canvas[x - 2][y + 4] = '|';
  24.     canvas[x - 2][y + 5] = ' ';
  25.     canvas[x - 2][y + 6] = '+';
  26.     canvas[x - 3][y] = '+';
  27.     canvas[x - 3][y + 1] = '-';
  28.     canvas[x - 3][y + 2] = '-';
  29.     canvas[x - 3][y + 3] = '-';
  30.     canvas[x - 3][y + 4] = '+';
  31.     canvas[x - 3][y + 5] = ' ';
  32.     canvas[x - 3][y + 6] = '|';
  33.     canvas[x - 4][y + 1] = '/';
  34.     canvas[x - 4][y + 2] = ' ';
  35.     canvas[x - 4][y + 3] = ' ';
  36.     canvas[x - 4][y + 4] = ' ';
  37.     canvas[x - 4][y + 5] = '/';
  38.     canvas[x - 4][y + 6] = '|';
  39.     canvas[x - 5][y + 2] = '+';
  40.     canvas[x - 5][y + 3] = '-';
  41.     canvas[x - 5][y + 4] = '-';
  42.     canvas[x - 5][y + 5] = '-';
  43.     canvas[x - 5][y + 6] = '+';
  44. }
  45. int main() {
  46.     cin >> m >> n;
  47.     k = 2 * m + 4 * n + 1;
  48.     for (int i = 1; i <= 1000; i++)
  49.         for (int j = 1; j <= 1000; j++)
  50.             canvas[i][j] = 46; //初始化画布
  51.     for (int i = 1; i <= m; i++)
  52.         for (int j = 1; j <= n; j++) {
  53.             cin >> num[i][j];
  54.             c = max(c, num[i][j] * 3 + 2 * (m - i + 1) + 1);
  55.         }
  56.     int x = 1, y = 1;
  57.     for (int i = 1; i <= m; i++)
  58.         for (int j = 1; j <= n; j++) {
  59.             x = c - 2 * (m - i);
  60.             y = 2 * (m - i) + 4 * (j - 1) + 1;
  61.             while (num[i][j] > 0) {
  62.                 
  63.                 draw(x, y);
  64.                 num[i][j]--;
  65.                 x -= 3;
  66.             }
  67.         }
  68.     for (int i = 1; i <= c; i++) {
  69.         for (int j = 1; j <= k; j++)
  70.             cout << canvas[i][j];
  71.         cout << endl;
  72.     }
  73.     return 0;
  74. }